//字符串 - 字符串相乘
//无进位相乘, 再相加
class Solution {
public:
    string multiply(string num1, string num2)
    {
        //无进位相乘
        int n = num1.size(), m = num2.size();
        vector<int> tmp(n + m - 1);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
    
        //再相加
        string ret;
        int cur = 0, i = n + m - 2; 
        while(i >= 0 || cur)
        {
            if(i >= 0) cur += tmp[i--];
            ret += cur % 10 + '0';
            cur /= 10;
        }

        //处理前导0        
        while(ret.back() == '0' && ret.size() > 1) ret.pop_back();
        
        //逆序返回
        reverse(ret.begin(), ret.end());
        return ret;
    }
};